package leetcode.code1609;

import java.util.LinkedList;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

/**
 * 执行用时：15 ms, 在所有 Java 提交中击败了40.87%的用户
 *
 * 内存消耗：76.7 MB, 在所有 Java 提交中击败了7.39%的用户
 *
 * 通过测试用例：105 / 105
 */
public class Solution implements IDebug {

	private int MAX = (int) 1e6 + 1;

	public boolean isEvenOddTree(TreeNode root) {
		Queue<TreeNode> q = new LinkedList<>();
		q.add(root);
		return this.f(q, 0);
	}

	private boolean f(Queue<TreeNode> q, int level) {
		Queue<TreeNode> next = new LinkedList<>();
		// 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
		if ((level & 1) == 0) {// 偶数
			int last = 0;
			while (!q.isEmpty()) {
				TreeNode tn = q.poll();
				if (tn.val <= last || (tn.val & 1) == 0) {
					return false;
				}
				last = tn.val;
				if (tn.left != null)
					next.add(tn.left);
				if (tn.right != null)
					next.add(tn.right);
			}
		} else {
			int last = MAX;
//			奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
			while (!q.isEmpty()) {
				TreeNode tn = q.poll();
				if (tn.val >= last || (tn.val & 1) == 1) {
					return false;
				}
				last = tn.val;
				if (tn.left != null)
					next.add(tn.left);
				if (tn.right != null)
					next.add(tn.right);
			}
		}
		if (next.isEmpty()) {
			return true;
		}
		return this.f(next, level + 1);
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
